/**
 * 31. 下一个排列
 * https://leetcode-cn.com/problems/next-permutation/
 */

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
function nextPermutation(nums) {
  const { length } = nums;
  let smallerIndex = length - 2;
  while (smallerIndex >= 0 && nums[smallerIndex] >= nums[smallerIndex + 1]) {
    smallerIndex -= 1;
  }
  if (smallerIndex < 0) {
    nums.reverse();
    return;
  }
  const smallerValue = nums[smallerIndex];
  let replaceIndex = length - 1;
  while (nums[replaceIndex] <= smallerValue) {
    replaceIndex -= 1;
  }
  nums[smallerIndex] = nums[replaceIndex];
  nums[replaceIndex] = smallerValue;
  let left = smallerIndex + 1;
  let right = length - 1;
  while (left < right) {
    const temp = nums[left];
    nums[left] = nums[right];
    nums[right] = temp;
    left += 1;
    right -= 1;
  }
}

let example;

example = [];
nextPermutation(example);
console.log(example.join(',') === '');

example = [1, 2, 3];
nextPermutation(example);
console.log(example.join(',') === '1,3,2');

example = [3, 2, 1];
nextPermutation(example);
console.log(example.join(',') === '1,2,3');

example = [1, 1, 5];
nextPermutation(example);
console.log(example.join(',') === '1,5,1');

example = [1];
nextPermutation(example);
console.log(example.join(',') === '1');

example = [1, 3, 2];
nextPermutation(example);
console.log(example.join(',') === '2,1,3');

example = [1, 5, 4, 3, 2];
nextPermutation(example);
console.log(example.join(',') === '2,1,3,4,5');

example = [2, 5, 4, 3, 2];
nextPermutation(example);
console.log(example.join(',') === '3,2,2,4,5');
